package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 1130. 叶值的最小代价生成树
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/25 11:16
 */
public class MctFromLeafValues {


    public static void main(String[] args) {
        MctFromLeafValues test = new MctFromLeafValues();

        // 77
//        int[] arr = {1, 2, 15, 3};

        // 2
//        int[] arr = {1,2};

        // 32
        int[] arr = {6, 2, 4};

        // 2691
//        int[] arr = {1, 2, 15, 3, 2, 3, 4, 2, 3, 4, 6, 12, 14, 2, 4, 9, 8, 15, 14, 11, 10, 9, 5, 15, 13, 12, 11, 5, 9, 8, 5, 4, 8};

        int i = test.mctFromLeafValues(arr);
        System.out.println(i);
    }

    public int mctFromLeafValues(int[] arr) {
        int length = arr.length;
        int[] sums = new int[length * length];
        int[] mm = new int[length * length];
        for (int i = length - 1; i >= 0; i--) {
            int index = i * length;
            mm[index + i] = arr[i];
            for (int j = i + 1; j < length; j++) {
                mm[index + j] = Math.max(mm[index + j - 1], arr[j]);
            }
        }
        for (int i = length - 2; i >= 0; i--) {
            int index = i * length;
            sums[index + i] = arr[i];
            sums[index + i + 1] = arr[i] * arr[i + 1];
            for (int j = i + 2; j < length; j++) {
                int v = Math.min(arr[i] * mm[(i + 1) * length + j] + sums[(i + 1) * length + j], arr[j] * mm[index + j - 1] + sums[index + j - 1]);
                for (int k = i + 1; k < j - 1; k++) {
                    v = Math.min(mm[index + k] * mm[(k + 1) * length + j] + sums[index + k] + sums[(k + 1) * length + j], v);
                }
                sums[index + j] = v;
            }
        }
        return sums[length - 1];
    }

}